#pragma once

//#include <algorithm>          // swap() -hez

#define FS_ISORT_MAX        32



// hasznalat: FastSort(array, 0, size - 1)

template <class T>
void FastSort(T *data, int left, int right)
{
    int n = right - left;

    if (n < FS_ISORT_MAX)
    {
        int i, j;


        for (i=left + 1; i<=right; i++)
        {
            T key = data[i];

            j = i-1;

            while (j >= left && key < data[j])
            {
                data[j + 1] = data[j];
                j--;
            }

            data[j + 1] = key;
        }                      

        return ;
    }

    int a, f;    

    a = left;
    f = right;
    
    T pivot(data[(a+f)/2]);

    do
    {
        while (data[a] < pivot) 
            a++;

        while (pivot < data[f]) 
            f--;

        if (a <= f)
        {
            //std::swap(data[a], data[f]);
            T tmp = data[a];
            data[a] = data[f];
            data[f] = tmp;
            a++;
            f--;
        }

    } while (a <= f);

    if (left < f)
        FastSort(data, left, f);

    if (a < right) 
        FastSort(data, a, right);
}


template <class T>
void FastSortPtr(T **data, int left, int right)
{
    int n = right - left;

    if (n < FS_ISORT_MAX)
    {
        int i, j;


        for (i=left + 1; i<=right; i++)
        {
            T *pKey = data[i];

            j = i-1;

            while (j >= left && *pKey < *data[j])
            {
                data[j + 1] = data[j];
                j--;
            }

            data[j + 1] = pKey;
        }                      

        return ;
    }

    int a, f;    

    a = left;
    f = right;
    T *pPivot = data[(a+f)/2];

    do
    {
        while (*data[a] < *pPivot) 
            a++;

        while (*pPivot < *data[f]) 
            f--;

        if (a <= f)
        {       
            T *tmp = data[a];
            data[a] = data[f];
            data[f] = tmp;
            a++;
            f--;
        }

    } while (a <= f);

    if (left < f)
        FastSortPtr(data, left, f);

    if (a < right) 
        FastSortPtr(data, a, right);    
}
